Indexes are ubiquitous in database environments, and many approaches exist to improve the performance of index lookup operations. For example, when B-Trees are utilized as the search structure, optimizations such as index lookaside and result caching have been used to improve the speed of index traversal by avoiding full traversals in cases where subsequent accesses tend to hit the same areas of the index tree. However, in cases where the lookups are truly random or appear to be random to the database system, it is often necessary to traverse the entire index tree, often at great cost. Known approaches are insufficient to address this problem. Buffer pools may be used to reduce the I/O needs for such traversals, however, the processor consumption/expense is often still very high. Hashed tables may be used instead of indexes, however, hashed approaches do not support range scans, non-equal lookups, and still suffer from random memory and page access penalties. Compression may be used to reduce the size of indexes in memory, however, large objects do not compress enough to greatly improve cache hit ratios. Contiguous buffer pools may be used to reduce the number of cache misses, improve the speed of finding a given page, and reduce the number of memory misses, however, there are still significant penalties for cache misses during traversal.